package com.ocean.tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * https://leetcode.cn/problems/cousins-in-binary-tree/
 * <p>
 * 二叉树的堂兄弟节点
 * <p>
 * 在同一深度 但父节点不同
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/02/14 <br>
 */
public class CousinsInBinaryTree2 {
    private TreeNode xParent;
    private TreeNode yParent;
    private int xDepth;
    private int yDepth;
    private int x;
    private int y;
    private boolean foundX = false;
    private boolean foundY = false;

    public static void main(String[] args) {
        CousinsInBinaryTree2 cousinsInBinaryTree = new CousinsInBinaryTree2();
        System.out.println(cousinsInBinaryTree.isCousins(TreeNode.getRoot(), 2, 3));
         cousinsInBinaryTree = new CousinsInBinaryTree2();
        System.out.println(cousinsInBinaryTree.isCousins(TreeNode.getRoot(), 4, 6));
    }

    /**
     * 广度优先
     *
     * @param root
     * @param x
     * @param y
     * @return
     */
    public boolean isCousins(TreeNode root, int x, int y) {
        this.x = x;
        this.y = y;
        dfs(root, 0, null);
        return xDepth == yDepth && xParent != yParent;
    }

    private void dfs(TreeNode node, int depth, TreeNode parent) {
        if (node == null) {
            return;
        }
        if (node.getValue() == x) {
            foundX = true;
            xParent = parent;
            xDepth = depth;
        }
        if (node.getValue() == y) {
            foundY = true;
            yParent = parent;
            yDepth = depth;
        }
        if (foundX && foundY) {
            return;
        }
        dfs(node.getLeft(), depth + 1, node);
        if (foundX && foundY) {
            return;
        }
        dfs(node.getRight(), depth + 1, node);
    }


}
